Leetcode 1035

It is a change of format for longest increase subsequence. You can only not cross by going forward only, and there is only two option, trying to connect curr number or give up on this number and go to next already.

class Solution {
    int[][] memo;
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        // to be as fast as possible we would want nums1 to be smaller
        if(nums1.length > nums2.length){
            return maxUncrossedLines(nums2,nums1);
        }
        int n = nums1.length;
        int m = nums2.length;
        memo = new int[n][m];
        for(int[] row : memo){
            Arrays.fill(row,-1);
        }
        return dp(nums1,nums2,0,0);
    }
    private int dp(int[] nums1, int[] nums2,int p1, int p2){
        // base case 
        // we have reached the end of either number
        if(p1 == nums1.length || p2 == nums2.length) return 0;
        
        // solved case
        if(memo[p1][p2] != -1) return memo[p1][p2];
        
        int res = 0;
        
        if(nums1[p1] == nums2[p2]){
            // we can connect them 
            res = 1 + dp(nums1,nums2,p1 + 1, p2 + 1);
        }else{
            // we cant connect them, we have two option
            // 1. we can skip the nums1 and not try to connect it 
            // 2. we can find the match number and connect nums2
            // note there is no going back 
            int skip = dp(nums1,nums2,p1 + 1, p2);
            int connect = dp(nums1,nums2,p1,p2 + 1);
            res = Math.max(skip,connect);
        }
        return memo[p1][p2] = res;
    }
}